//
//  归并排序.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/18.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/*
 相当于是快速排序的逆向操作
 归并排序：先假定拍好一个范围的元素，然后递归的认为排好了。
 然后回溯，连接排好的元素
 */
class SolutionMergeTrainTrain {
    func mergetSort(_ nums: inout [Int]) {
        partSort(&nums, left: 0, right: nums.count - 1)
    }
    func partSort(_ nums: inout [Int], left: Int, right: Int)  {
        if right <= left {
            return
        }
        let mid = (left + right) / 2
        partSort(&nums, left: left, right: mid)
        partSort(&nums, left: mid + 1, right: right)
        merge(&nums, left: left, mid: mid, right: right)
    }
    // 合并两个有序数组数组，合并两个有序数组也是有技巧的
    func merge(_ nums: inout [Int], left: Int,mid: Int, right: Int){
        var temp: [Int] = Array(repeating: 0, count: right - left + 1)
        var first = left
        var second = mid + 1
        var index = 0
        // 当其中任意一个解释时都会结束
        while first <= mid && second <= right{
            if nums[first] <= nums[second]  {
                temp[index] = nums[first]
                first += 1
            } else {
                temp[index] = nums[second]
                second += 1
            }
            index += 1
        }
        while first <= mid {
            temp[index] = nums[first]
            first += 1
            index += 1
        }
        while second <= right {
            temp[index] = nums[second]
            second += 1
            index += 1
        }
        
        for i in 0..<temp.count {
            nums[left + i] = temp[i]
        }
    }
    
    static func test() {
        var nums = [1, 11, 8, 2, 11, 4, 1, 5 , 7, 10, 3]
        let solution = SolutionMergeTrainTrain()
        solution.mergetSort(&nums)
        print(nums)
    }
}
